#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <iostream>
#include <istream>

using ll = int64_t;
using std::cin, std::cout;

const ll maxn = 1e6+5;
ll n, kds[maxn], m, anss[maxn], viss[maxn], bits[maxn];

struct Sch{
    ll l, r, pos;
}schs[maxn];

ll lb(const ll &v){
    return v&(-v);
}

void tadd(ll idx, const ll &v){
    while(idx<=n){
        bits[idx]+=v;
        idx+=lb(idx);
    }
}

ll tpsch(ll idx){
    ll res{};
    while(idx!=0){
        res+=bits[idx];
        idx-=lb(idx);
    }
    return res;
}

int main(){
    std::iostream::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin>>n;
    for(ll i{1};i<=n;i++){
        cin>>kds[i];
    }
    cin>>m;
    for(ll i{1};i<=m;i++){
        cin>>schs[i].l>>schs[i].r;
        schs[i].pos=i;
    }
    std::sort(schs+1, schs+1+m, [](const Sch &a, const Sch &b)->bool{
        return a.r<b.r;
    });
    ll nm{1};
    for(ll i{1};i<=n;i++){
        if((bool)viss[kds[i]]){
            tadd(viss[kds[i]], -1);
            viss[kds[i]]=i;
            tadd(i, 1);
        }else{
            viss[kds[i]]=i;
            tadd(i, 1);
        }
        if(i==schs[nm].r){
            top:;
            anss[schs[nm].pos] = tpsch(schs[nm].r) - tpsch(schs[nm].l-1);
            if(nm==m)break;
            nm++;
            if(schs[nm].r==schs[nm-1].r)goto top;
        }
    }
    for(ll i{1};i<=m;i++){
        cout<<anss[i]<<'\n';
    }
}